package main

func maxProfit(prices []int) int {

	getMinStack := func(arr []int) []int {
		if len(arr) <= 0 {
			return nil
		}
		data := make([]int, len(arr))
		data[len(data)-1] = arr[len(data)-1]
		for i := len(arr) - 2; i >= 0; i-- {
			if arr[i] < data[i+1] {
				data[i] = arr[i]
			} else {
				data[i] = data[i+1]
			}
		}

		return data
	}

	max := 0
	stack := getMinStack(prices)
	for i := 0; i < len(prices)-1; i++ {
		if prices[i] > stack[i+1] {
			if prices[i]-stack[i+1] > max {
				max = prices[i] - stack[i+1]
			}
		}
	}

	return max
}
